/**
 * Combination.java
 * @author: liuex
 * 2008-3-9 ����07:50:29
 *
 * note: 
 */
package org.lex.tf;

import java.util.*;

/**
 * Immuteable
 */
public class Combination<T> implements Iterator<List<T>>
{
	private List<List<T>> lists = null;
	private Iterator<List<T>> iter = null;

	@SuppressWarnings( "unchecked" )
	public Combination( int r, Collection<T> src )
	{
		this( src.toArray( (T[]) new Object[0] ), r );
	}

	public Combination( int r, T ... srcs )
	{
		this( Arrays.copyOf( srcs, srcs.length ), r );
	}

	@Override
	public boolean hasNext()
	{
		return iter.hasNext();
	}

	@Override
	public List<T> next()
	{
		return iter.next();
	}

	@Override
	public void remove() throws UnsupportedOperationException
	{
		throw new UnsupportedOperationException( "Combination is immuteable" );
	}

	private Combination( T[] src, int r )
	{
		this.lists = this.C( new SimpleSkipList<T>( src ), r );
		this.iter = lists.iterator();
	}

	private List<List<T>> C( SkipList<T> src, int r )
	{
		if( r < 1 )
			return null;
		if( 1 == r )
		{
			// C(n, 1)
			List<List<T>> lists = new ArrayList<List<T>>( src.size() );
			for( int i = 0; i < src.size(); i++ )
			{
				T e = src.get( i );
				List<T> l = new LinkedList<T>();
				l.add( e );
				lists.add( l );
			}
			return lists;
		}
		else
		{
			// C(n,r) where r > 1
			List<List<T>> lists = new LinkedList<List<T>>();
			for( int i = 0; i < src.size(); i++ )
			{
				T e = src.get( i );
				SkipList<T> skipList = new ArraySkipList<T>( src, i );
				List<List<T>> listList = this.C( skipList, r - 1 );
				for( Iterator<List<T>> iter = listList.iterator(); iter.hasNext(); )
				{
					List<T> list = iter.next();
					list.add( 0, e );
					lists.add( list );
				}
			}
			return lists;
		}
	}

	
}
